МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ШИФРУВАННЯ ТА РОЗШИФРУВАННЯ ІНФОРМАЦІЇ ЗА ДОПОМОГОЮ АЛГОРИТМУ RSA. МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 5 З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” Затверджено на засiданнi кафедри “Безпека інформаційних технологій”, протокол № від 2012 р. Львів – 2012  Шифрування та розшифрування інформації за допомогою алгоритму RSA: Методичні вказівки до лабораторної роботи №5 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 11 с. Укладачі: А.Е.Лагун, к.т.н., доцент А.В.Петришин, асистент Відповідальний за випуск: Л.В. Мороз, к.т.н., доцент. Рецензент: В.М.Максимович, д.т.н., професор. Мета роботи – вивчити математичні основи побудови алгоритму шифрування RSA, методи криптоаналізу та вимоги до стійкості алгоритму RSA, навчитися розробляти програмне забезпечення для шифрування та цифрового підпису з використанням алгоритму RSA. 1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ Безпека RSA базується на складності розкладу на множники великих чисел. Відкритий та закритий ключі є функціями двох великих (більше двохсот десяткових розрядів) простих чисел. Відновлення відкритого тексту за шифротекстом і відкритим ключем еквівалентне розкладу на множники двох великих чисел. Для генерації двох ключів використовуються два великих випадкових простих числа p і q однакової довжини. Розширений алгоритм Евкліда використовується для обчислення ключа розшифрування d такого, що ed=1(mod(p-1)(q-1)). (1) Іншими словами d=e-1mod((p-1)(q-1)) (2) d і n=pq є взаємно простими числами. Числа e і n – це відкритий ключ, а число d – закритий. Для шифрування повідомлення m воно спочатку розбивається на цифрові блоки, які менші за n (для двійкових даних вибирається найбільший степінь числа 2, менший за n). А саме, якщо p і q – 100-розрядні прості числа, то n буде мати приблизно 200 розрядів і кожен блок повідомлення mi повинен мати також приблизно 200 розрядів. Зашифроване повідомлення c буде складатися з блоків ci такої ж довжини. Формула шифрування має вигляд: ci=mie mod n (3) Для розшифрування повідомлення береться кожен зашифрований блок ci і обчислюється mi=cid mod n (4) Оскільки cid=(mie)d=mied=mik(p-1)(q-1)+1=mimik(p-1)(q-1)=mi*1=mi то формула відновлює повідомлення. Для піднесення до степеня за модулем n використовується бінарний алгоритм: Задано:
. Обчислити:
. Вважається, що d < n. Алгоритм у вигляді прямолінійної програми для обчислення функції
має вигляд. Показник
подається у двійковій системі числення:
, де
і
. Присвоюється
. Тоді
-та команда задається так:
Всього команд
. Результатом виконання останньої є
Всього витрачається
множень. Нехай p=47, q=71. Тоді N=pq=3337. Ключ e не повинен мати спільних множників (p-1)(q-1)=46*70=3220 Вибираємо випадково e, наприклад, 79. Тоді d=79-1mod 3220=1019. Під час обчислення використаний розширений алгоритм Евкліда. Зробимо e і n загальнодоступними, а d збережемо в секреті. Відкидаємо p і q. Для шифрування повідомлення m=6882326879666683 спочатку розбиваємо його на малі блоки. Для розглянутого випадку використовуємо трибуквенні блоки. Повідомлення розіб’ється на шість блоків mi. m1=688 m2=232 m3=687 m4=966 m5=668 m6=003 Перший блок шифрується 68879 mod 3337=1570=c1. Виконуючи такі самі операції для наступних бітів, одержимо шифротекст повідомлення: c=1570 2756 2091 2276 2423 158 Для розшифрування потрібно виконати операцію піднесення до степеня, використовуючи ключ розшифрування 1019: 15701019 mod 3337 =688 =m1 Аналогічно відновлюється інша частина повідомлення. Швидкодія RSA. Апаратно RSA приблизно в 1000 разів повільніший за алгоритм симетричного шифрування DES. Програмно DES приблизно в 100 разів швидший, ніж ...